# 线性查找
import time

list1 = [1, 3, 2, 7, 9, 11, 4, 56, 9, -2]
list2 = [1, 2, 3, 7, 9, 11, 12, 56, 78, 89]


# 线性查找对每个数据依次进行遍历，找到后返回找不到返回-1  时间复杂度为O(n) 线性阶
def linear_search(ls, value):
    start_time = int(round(time.time() * 1000))
    for index, v in enumerate(ls):
        if v == value:
            print(int(round(time.time() * 1000)) - start_time)
            return index
    return -1


# 二分法查找 前提必须是有序的存储结构 时间复杂度:O(log2n) 对数阶
def binary_search(ls, value):
    start_time = int(round(time.time() * 1000))
    left = 0
    right = len(ls) - 1
    while left <= right:
        mid = (left + right) // 2
        if ls[mid] == value:
            print(int(round(time.time() * 1000)) - start_time)
            return mid
        # 说明值在左边
        elif ls[mid] > value:
            right = mid - 1
        # 说明值在右侧
        elif ls[mid] < value:
            left = mid + 1
    return -1


print(binary_search(list(range(100000000)), 999999))
